package algorithm.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * @author SeonExlike
 * @since 2024/4/16
 */
public class NO77_组合 {
    public static void main(String[] args) {
        List<List<Integer>> combine = new Solution().combine(3, 3);
        System.out.println(combine);
    }
    static class Solution {

        List<List<Integer>> result;

        LinkedList<Integer> path;

        public List<List<Integer>> combine(int n, int k) {
            result = new ArrayList<>();
            path = new LinkedList<>();
            backtrack(n, k, 1);
            return result;
        }

        /**
         * for循环就是遍历序列，可以理解为一个节点有多少个子孩子，这个for循环就执行多少次。就是横向的遍历。
         * 简要的一句话就是 : 回溯法一般是在一个序列中做选择，序列的大小构成了树的宽度，递归的深度（终止条件的达成难度）构成了树的深度！！！
         */
        private void backtrack(int n, int k, int start) {
            if (path.size() == k) {
                result.add(new ArrayList<>(path));
                return;
            }
            for (int i = start; i <= n; i++) {
                // 回溯添加条件
                path.addLast(i);
                // 递归
                backtrack(n, k, i + 1);
                // 回溯撤销已经探索的节点
                path.removeLast();
            }
        }
    }
}
